package flashBack;

/**
 * @author zxc
 * @date 2023/01/16 10:16
 **/

import java.util.LinkedList;
import java.util.List;

/**
 * 题目 ：包含k个元素的组合
 * 题目形式 ：
 * 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
 */
public class Combine {
    /**
     * 思路 ：
     * （1）由于是组合，所以子数组中数字之间的顺序并不影响；
     * （2）类似于求子集（只不过是求数组中，元素个数为k的子数组）
     */
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new LinkedList<>();
        flushBackNumber(n , k , 1 , new LinkedList<Integer>() , result);
        return result;
    }
    // 回溯法 ：获取数字为[1 , n]范围内，获取所有符合条件（子数组中元素个数为k）子数组;
    private void flushBackNumber(int n, int k, int index, LinkedList<Integer> subset, List<List<Integer>> result) {
        // （1）此处为，判断subset解状态是否满足条件，若是满足条件的话，则将subset的拷贝加入到result集合中;
//        if(index == n + 1){ // 1.首先，判断是否已经获取到获取到一个解状态；
            if(subset.size() == k){
                // 2.其次，判断此解状态是否满足题目要求（即，解状态subset中元素个数是否为k）;
                // result集合中所需要存储的是，当前subset解状态的拷贝
                result.add(new LinkedList<>(subset));
            }
//        }
        // 注意 ：n个步骤，是通过index来进行控制;
        // (2)此处是回溯法寻找子集的核心部分（会遍历寻找到所有集合，若是找到符合条件的解状态就会就会将其加入到result集合中）;
        else if(index <= n){
            // 为判断是否已经获取到一个解状态，即需要index <= n;
            // 若是index > n,即代表已经获取到解状态（即，已经经历过n个步骤），没必要向下遍历;
            // 选择 ：不将当前遍历的元素index插入到subset解状态
            flushBackNumber(n , k , index + 1, subset , result);

            // 选择 ：将当前遍历的元素index插入到subset解状态
            subset.add(index);
            flushBackNumber(n , k , index + 1, subset , result);
            // 回溯 ：即将上面插入到解状态的index移除;
            subset.removeLast();
        }
    }
    /**
     * 分析 ：
     * 时间复杂度 ：O（2的n次方）
     * （注意 ：由于使用了回溯算法，即基本上时间复杂度为O（2的n次方）;）
     */
}
